
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

// 二叉树节点定义
typedef struct BtreeNode {
    DataType data;  // 元素本身的数据
    struct BtreeNode *lchild, *rchild;  // 左孩子和右孩子指针
} BtreeNode, *Btree;

// 创建新节点
Btree createNode(DataType data) {
    Btree newNode = (Btree)malloc(sizeof(BtreeNode));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->lchild = NULL;
        newNode->rchild = NULL;
    }
    return newNode;
}

// 前序遍历
void preOrder(Btree T) {
    if (T != NULL) {
        printf("%d ", T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

// 中序遍历
void inOrder(Btree T) {
    if (T != NULL) {
        inOrder(T->lchild);
        printf("%d ", T->data);
        inOrder(T->rchild);
    }
}


// 后序遍历
void postOrder(Btree T) {
    if (T != NULL) {
        postOrder(T->lchild);
        postOrder(T->rchild);
        printf("%d ", T->data);
    }
}

// 非递归中序遍历


int main() {
    // 创建示例二叉树: 
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    #ifdef _WIN32
        system("chcp 65001 > null");
    #endif

    Btree root = createNode(1);
    root->lchild = createNode(2);
    root->rchild = createNode(3);
    root->lchild->lchild = createNode(4);
    root->lchild->rchild = createNode(5);

    printf("前序遍历结果: ");
    preOrder(root);
    printf("\n");

    printf("中序遍历结果: ");
    inOrder(root);
    printf("\n");

    printf("后序遍历结果: ");
    postOrder(root);
    printf("\n");

    return 0;
}
